/**
 * 题干
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 *
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 * https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
 *
 * 思路
 * 第一反应是用堆
 * 当然更为简单的想法是使用排序，然后再取第k个
 *
 * @date 2021-11-20.
 * @author X.
 *
 * 排序
 * 时间复杂度O(nlogn)
 * 空间复杂度O(logn)
 *
 * 堆
 * 时间复杂度：O(NlogK)，遍历数据O(N)，堆内元素调整O(K)；
 * 空间复杂度：O(K)。
 *
 *
 */
public class FindKthLargest215 {

    // 排序
    public int findKthLargest1(int[] nums, int k) {
        if (nums == null || nums.length < k) {
            return -1;
        }
        Arrays.sort(nums);
        return nums[nums.length - k];
    }

    // 堆
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length < k) {
            return -1;
        }
        // 维护一个包含k个元素的最小堆
        // 如果当前堆不满，直接添加；
        // 堆满的时候，如果新读到的数小于等于堆顶，肯定不是我们要找的元素，
        // 只有新遍历到的数大于堆顶的时候，才将堆顶拿出，然后放入新读到的数，进而让堆自己去调整内部结构。

        PriorityQueue<Integer> queue = new PriorityQueue<>(k, (a,b) -> a-b);
        for (int i = 0; i < k; i++) {
            queue.offer(nums[i]);
        }

        for (int i = k; i < nums.length; i++) {
            int top = queue.peek();
            if (nums[i] > top) {
                queue.poll();
                queue.offer(nums[i]);
            }
        }

        return queue.peek();
    }
}
